package com.leetcode;

public class LongestValidParentheses
{

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		System.out.println(longestValidParentheses("()))()()()()()))))))"));
	}

	public static int longestValidParentheses(String str)
	{
		if (str == null || str.length() == 0)
			return 0;
		int max = 0;
		int total = 0;
		int numberofLeftParentheses = 0;
		for (int k = 0; k < str.length(); k++)
		{
			if (str.charAt(k) == '(')
			{
				numberofLeftParentheses++;
				total++;
			}
			else
			{
				numberofLeftParentheses--;
				total++;
			}
			if (numberofLeftParentheses == 0 && max < total)
			{
				max = total;
			}
			if (numberofLeftParentheses < 0)
			{
				total = 0;
				numberofLeftParentheses = 0;
			}
		}
		total = 0;
		numberofLeftParentheses = 0;
		for (int k = str.length() - 1; k >= 0; k--)
		{
			if (str.charAt(k) == ')')
			{
				numberofLeftParentheses++;
				total++;
			}
			else
			{
				numberofLeftParentheses--;
				total++;
			}
			if (numberofLeftParentheses == 0 && max < total)
			{
				max = total;
			}
			if (numberofLeftParentheses < 0)
			{
				total = 0;
				numberofLeftParentheses = 0;
			}
		}
		return max;
	}

	// this method will return total number of valid pare of parentheses (not
	// continuous).
	public static int totalValidPairOfParentheses(String str)
	{
		if (str == null || str.length() == 0)
			return 0;
		int total = 0;
		int numberofLeftParentheses = 0;
		for (int k = 0; k < str.length(); k++)
		{
			if (str.charAt(k) == '(')
			{
				numberofLeftParentheses++;
			}
			else
			{
				if (numberofLeftParentheses > 0)
				{
					numberofLeftParentheses--;
					total++;
				}
			}
		}
		return total;
	}

}
